//-------------------------------------------
// * AddPrefix
//-------------------------------------------
// This routine constitutes the heart of the algorithm.
// It is called repetitively, once for each of the prefixes
// of the input string.  The prefix in question is denoted
// by the index of its last character.
//
// At each prefix, we start at the active point, and add
// a new edge denoting the new last character, until we
// reach a point where the new edge is not needed due to
// the presence of an existing edge starting with the new
// last character.  This point is the end point.
//
// Luckily for us, the end point just happens to be the
// active point for the next pass through the tree.  All
// we have to do is update it's mLastCharIdx to indicate
// that it has grown by a single character, and then this
// routine can do all its work one more time.
//


void
SuffixTree::EdgeExists(Suffix &active,int CharIdx,Edge *pEdge)
{
  
  pEdge = GetEdge(active.mOriginNode,mSoruce[CharIdx]);
  
}

void 
SuffixTree::AddPrefix( Suffix &active, long LastCharIdx )
{
  register long ParentNode;
  register long LastParentNode = -1;
	
  register Edge *pEdge;
  ParentNode = active.mOriginNode;
  while(!EdgeExists(active,LastCharIdx,pEdge)){

	 // If the edge is implicit, need to split it before adding new leaf edge. 
	 if (active.Implicit()){
		ParentNode = SplitEdge(pEdge,active);
	 }
	 AddNewLeafEdge(LastCharIdx,mMaxSourceIndex,ParentNode,-1);

  }


   for ( ; ; ) {
		register Edge *pEdge;
      ParentNode = active.mOriginNode;

		// Step 1 is to try and find a matching edge for the given node.
		// If a matching edge exists, we are done adding edges, so we break
		// out of this big loop.
		if ( active.Explicit() ) {
			if (active.mOriginNode < 0){
        		cout<<"Eureka"<<endl;
        	}
        
   		pEdge = GetEdge(active.mOriginNode,mSource[LastCharIdx]);  	        
        	if (EdgeValid(pEdge)) break;

    	} else { //implicit node, a little more complicated
 			pEdge = GetEdge(active.mOriginNode,mSource[active.mFirstCharIdx]);
			long span = active.mLastCharIdx - active.mFirstCharIdx;
			cout<<"**Span="<<span<<endl;
			// Is there a matching "edge"?  If so, done with this iteration...
 			if ( mSource[ pEdge->mFirstCharIdx + span + 1 ] == mSource[ LastCharIdx ] )
				  break;

			// Otherwise, it's time for a split...
			ParentNode = SplitEdge(pEdge,active);
		}

		// If we didn't break out of this loop, we didn't find a matching edge, 
		// so we create a new one, add it to the tree at the parent node position, 
		// and insert it into the hash table.  When we create a new node, it also
		// means we need to create a suffix link to the new node from
		// the last node we visited.

    	// Create a new leaf edge... this includes creating the leaf node as
		// well as inserting the new edge into the parent (newStartNode).      
        AddNewLeafEdge(LastCharIdx,mMaxSourceIndex,ParentNode,-1);
          
        if ( LastParentNode > 0 )
            mNodes[ LastParentNode ].mSuffixNode = ParentNode;
      
        LastParentNode = ParentNode;

		// This final step is where we move to the next smaller suffix
        if ( active.mOriginNode == 0 ){
            active.mFirstCharIdx++;
        }else{
        	if (mNodes[active.mOriginNode].mSuffixNode <0){
        		cout<<"Attempt to follow a non-valid suffix link. \n";
        	}
        
            active.mOriginNode = mNodes[ active.mOriginNode ].mSuffixNode;
        }
        CanonizeSuffix(&active);
    }

    if ( LastParentNode > 0 )
        mNodes[ LastParentNode ].mSuffixNode = ParentNode;
    active.mLastCharIdx++;  //Now the endpoint is the next active point
    
    CanonizeSuffix(&active);

}
